1. Field
The present application relates to video encoders and cost functions employed therein.
2. Background
Video compression involves compression of digital video data. Video compression is used for efficient coding of video data in video file formats and streaming video formats. Compression is a reversible conversion of data to a format with fewer bits, usually performed so that the data can be stored or transmitted more efficiently. If the inverse of the process, decompression, produces an exact replica of the original data then the compression is lossless. Lossy compression, usually applied to image data, does not allow reproduction of an exact replica of the original image, but it is more efficient. While lossless video compression is possible, in practice it is virtually never used. Standard video data rate reduction involves discarding data.
Video is basically a three-dimensional array of color pixels. Two dimensions serve as spatial (horizontal and vertical) directions of the moving pictures, and one dimension represents the time domain.
A frame is a set of all pixels that (approximately) correspond to a single point in time. Basically, a frame is the same as a still picture. However, in interlaced video, the set of horizontal lines with even numbers and the set with odd numbers are grouped together in fields. The term “picture” can refer to a frame or a field.
Video data contains spatial and temporal redundancy. Similarities can thus be encoded by merely registering differences within a frame (spatial) and/or between frames (temporal). Spatial encoding is performed by taking advantage of the fact that the human eye is unable to distinguish small differences in color as easily as it can changes in brightness, and so very similar areas of color can be “averaged out.” With temporal compression, only the changes from one frame to the next are encoded because a large number of the pixels will often be the same on a series of frames.
Video compression typically reduces this redundancy using lossy compression. Usually this is achieved by (a) image compression techniques to reduce spatial redundancy from frames (this is known as intraframe compression or spatial compression) and (b) motion compensation and other techniques to reduce temporal redundancy (known as interframe compression or temporal compression).
H.264/AVC is a video compression standard resulting from joint efforts of ISO (International Standards Organization) and ITU (International Telecommunication Union.) FIG. 1 shows a block diagram for an H.264/AVC encoder. An input video frame 102 is divided into macroblocks 104 and fed into system 100. For each macroblock 104, a predictor 132 is generated and subtracted (as shown by reference numeral 106 of FIG. 1) from the original macroblock 104 to generate a residual 107. This residual 107 is then transformed 108 and quantized 110. The quantized macroblock is then entropy coded 112 to generate a compressed bitstream 113. The quantized macroblock is also inverse-quantized 114, inverse-transformed 116 and added back to the predictor by adder 118. The reconstructed macroblock is filtered on the macroblock edges with a deblocking filter 120 and then stored in memory 122.
Quantization, in principle, involves reducing the dynamic range of the signal. This impacts the number of bits (rate) generated by entropy coding. This also introduces loss in the residual, which causes the original and reconstructed macroblock to differ. This loss is normally referred to as quantization error (distortion). The strength of quantization is determined by a quantization factor parameter. The higher the quantization parameter, the higher the distortion and lower the rate.
As discussed above, the predictor can be of two types—intra 128 and inter 130. Spatial estimation 124 looks at the neighboring macroblocks in a frame to generate the intra predictor 128 from among multiple choices. Motion estimation 126 looks at the previous/future frames to generate the inter predictor 130 from among multiple choices. Inter predictor aims to reduce temporal redundancy. Typically, reducing temporal redundancy has the biggest impact on reducing rate.
Motion estimation may be one of the most computationally expensive blocks in the encoder because of the huge number of potential predictors it has to choose from. Practically, motion estimation involves searching for the inter predictor in a search area comprising a subset of the previous frames. Potential predictors or candidates from the search area are examined on the basis of a cost function or metric. Once the metric is calculated for all the candidates in the search area, the candidate that minimizes the metric is chosen as the inter predictor. Hence, the main factors affecting motion estimation are: search area size, search methodology, and cost function.
Focusing particularly on cost function, a cost function essentially quantifies the redundancy between the original block of the current frame and a candidate block of the search area. The redundancy should ideally be quantified in terms of accurate rate and distortion.
The cost function employed in current motion estimators is Sum-of-Absolute-Difference (SAD). FIG. 2 shows how SAD is calculated. Frame(t) 206 is the current frame containing a macroblock 208 which is stored in Encode MB (MACROBLOCK) RAM 212. Frame(t−1) 202 is the previous frame containing a search area 204 which is stored in Search RAM 210. It is appreciated that more than one previous frame can be used.
In the example in FIG. 2, the search area 204 size is M×N. Let the size of the blocks being considered be A×B, where A and B are defined in Table 1. Let the given block 208 from the current frame 206 be denoted as c 215. Let each candidate from the search area 204 be denoted as p(x,y) 214, where xε[0,N] and yε[0,M]. (x,y) represents a position in the search area 214.
TABLE 1Notations for e(x, y) for different block shapesAB      z    ⁢    ε    ⁡      [          0      ,                                    A            ×            B                    16                -        1              ]  Notation 4 4zε[0, 0]e(x, y) = [e(x, y, 0)] 8 4zε[0, 1]e(x, y) = [e(x, y, 0) e(x, y, 1)]  4 8zε[0, 1]      e    ⁡          (              x        ,        y            )        =      [                                        e            ⁡                          (                              x                ,                y                ,                0                            )                                                                        e            ⁡                          (                              x                ,                y                ,                1                            )                                            ]    8 8zε[0, 3]      e    ⁡          (              x        ,        y            )        =      [                                        e            ⁡                          (                              x                ,                y                ,                0                            )                                                            e            ⁡                          (                              x                ,                y                ,                1                            )                                                                        e            ⁡                          (                              x                ,                y                ,                2                            )                                                            e            ⁡                          (                              x                ,                y                ,                3                            )                                            ]   16 8zε[0, 7]      e    ⁡          (              x        ,        y            )        =      [                                        e            ⁡                          (                              x                ,                y                ,                0                            )                                                            e            ⁡                          (                              x                ,                y                ,                1                            )                                                            e            ⁡                          (                              x                ,                y                ,                2                            )                                                            e            ⁡                          (                              x                ,                y                ,                3                            )                                                                        e            ⁡                          (                              x                ,                y                ,                4                            )                                                            e            ⁡                          (                              x                ,                y                ,                5                            )                                                            e            ⁡                          (                              x                ,                y                ,                6                            )                                                            e            ⁡                          (                              x                ,                y                ,                7                            )                                            ]    816zε[0, 7]      e    ⁡          (              x        ,        y            )        =      [                                        e            ⁡                          (                              x                ,                y                ,                0                            )                                                            e            ⁡                          (                              x                ,                y                ,                1                            )                                                                        e            ⁡                          (                              x                ,                y                ,                2                            )                                                            e            ⁡                          (                              x                ,                y                ,                3                            )                                                                        e            ⁡                          (                              x                ,                y                ,                4                            )                                                            e            ⁡                          (                              x                ,                y                ,                5                            )                                                                        e            ⁡                          (                              x                ,                y                ,                6                            )                                                            e            ⁡                          (                              x                ,                y                ,                7                            )                                            ]   1616zε[0, 15]      e    ⁡          (              x        ,        y            )        =      [                                        e            ⁡                          (                              x                ,                y                ,                0                            )                                                            e            ⁡                          (                              x                ,                y                ,                1                            )                                                            e            ⁡                          (                              x                ,                y                ,                2                            )                                                            e            ⁡                          (                              x                ,                y                ,                3                            )                                                                        e            ⁡                          (                              x                ,                y                ,                4                            )                                                            e            ⁡                          (                              x                ,                y                ,                5                            )                                                            e            ⁡                          (                              x                ,                y                ,                6                            )                                                            e            ⁡                          (                              x                ,                y                ,                7                            )                                                                        e            ⁡                          (                              x                ,                y                ,                8                            )                                                            e            ⁡                          (                              x                ,                y                ,                9                            )                                                            e            ⁡                          (                              x                ,                y                ,                10                            )                                                            e            ⁡                          (                              x                ,                y                ,                11                            )                                                                        e            ⁡                          (                              x                ,                y                ,                12                            )                                                            e            ⁡                          (                              x                ,                y                ,                13                            )                                                            e            ⁡                          (                              x                ,                y                ,                14                            )                                                            e            ⁡                          (                              x                ,                y                ,                15                            )                                            ]  
The following steps are calculated to get a motion vector (X,Y):
c is motion compensated 216 for by p(x,y) 214 to get a residual error signal 218, e(x,y)e(x,y)=p(x,y)−c  (1)SAD 222 is then calculated 220 from e(x,y).
                              SAD          ⁡                      (                          x              ,              y                        )                          =                                            ∑                              i                ,                j                                      ⁢                                                                            e                  ⁡                                      (                                          x                      ,                      y                                        )                                                                              ⁢                                                          ⁢              where              ⁢                                                          ⁢              i                                ∈                                    [                              0                ,                A                            ]                        ⁢                                                  ⁢            and            ⁢                                                  ⁢            j                    ∈                      [                          0              ,              B                        ]                                              (        2        )            The motion vector (X,Y) is then calculated from SAD(x,y).(X,Y)=(x,y)|min SAD(x,y)  (3)
Ideally, the predictor macroblock partition should be the macroblock partition that most closely resembles the macroblock. One of the drawbacks of SAD is that it does not specifically and accurately account for Rate and Distortion. Hence the redundancy is not quantified accurately, and therefore it is possible that the predictive macroblock partition chosen is not the most efficient choice. Thus, in some cases utilizing a SAD approach may actually result in less than optimal performance.